{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ML_in_Finance-Viterbi\n",
    "# Author: Matthew Dixon\n",
    "# Version: 1.0 (24.7.2019)\n",
    "# License: MIT\n",
    "# Email: matthew.dixon@iit.edu\n",
    "# Notes: tested on Mac OS X with Python 3.6 and Tensorflow 1.3.0\n",
    "# Citation: Please cite the following reference if this notebook is used for research purposes:\n",
    "# Bilokon P., Dixon M.F. and I. Halperin, Machine Learning in Finance: From Theory to Practice, Springer Graduate textbook Series, 2020. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def viterbi(sequence_of_observations, states, initial_probabilities, transition_probabilities, emission_probabilities):\n",
    "    V = [{}]\n",
    "    for s in states:\n",
    "        V[0][s] = {\n",
    "            'probability': initial_probabilities[s] * emission_probabilities[s][sequence_of_observations[0]],\n",
    "            'previous': None}\n",
    "    for t in range(1, len(sequence_of_observations)):\n",
    "        V.append({})\n",
    "        for s in states:\n",
    "            max_tr_probability = V[t-1][states[0]]['probability'] * transition_probabilities[states[0]][s]\n",
    "            previous_s_selected = states[0]\n",
    "            for previous_s in states[1:]:\n",
    "                tr_probability = V[t-1][previous_s]['probability'] * transition_probabilities[previous_s][s]\n",
    "                if tr_probability > max_tr_probability:\n",
    "                    max_tr_probability = tr_probability\n",
    "                    previous_s_selected = previous_s        \n",
    "            max_probability = max_tr_probability * emission_probabilities[s][sequence_of_observations[t]]\n",
    "            V[t][s] = {'probability': max_probability, 'previous': previous_s_selected}                    \n",
    "    most_likely_states = []\n",
    "    max_probability = max(value['probability'] for value in V[-1].values())\n",
    "    previous = None\n",
    "    for s, data in V[-1].items():\n",
    "        if data['probability'] == max_probability:\n",
    "            most_likely_states.append(s)\n",
    "            previous = s\n",
    "            break\n",
    "    for t in range(len(V) - 2, -1, -1):\n",
    "        most_likely_states.insert(0, V[t + 1][previous]['previous'])\n",
    "        previous = V[t + 1][previous]['previous']\n",
    "    return {'steps': most_likely_states, 'max_probability': max_probability}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sequence_of_observations = ['Heads', 'Tails', 'Tails', 'Heads', 'Tails', 'Heads', 'Heads', 'Heads', 'Tails', 'Heads']\n",
    "states = ['Fair', 'Loaded']\n",
    "initial_probabilities = {'Fair': 0.6, 'Loaded': 0.4}\n",
    "transition_probabilities = {\n",
    "    'Fair': {'Fair': 0.6, 'Loaded': 0.4},\n",
    "    'Loaded': {'Fair': 0.4, 'Loaded': 0.6}\n",
    "}\n",
    "emission_probabilities = {\n",
    "    'Fair': {'Heads': 0.5, 'Tails': 0.5},\n",
    "    'Loaded': {'Heads': 0.8, 'Tails': 0.2}\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'max_probability': 1.146617856e-05,\n",
       " 'steps': ['Fair',\n",
       "  'Fair',\n",
       "  'Fair',\n",
       "  'Fair',\n",
       "  'Fair',\n",
       "  'Loaded',\n",
       "  'Loaded',\n",
       "  'Loaded',\n",
       "  'Fair',\n",
       "  'Loaded']}"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "viterbi(sequence_of_observations,\n",
    "        states,\n",
    "        initial_probabilities,\n",
    "        transition_probabilities,\n",
    "        emission_probabilities)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
